//
//  shannon_fano.c
//  ShannonFano
//
//  Created by Alessio Scannapieco on 17.11.11.
//  Copyright 2011 SUPSI - Manno. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

#include "shannon_fano.h"
#include "node.h"

#define MAX_LENGTH_CODE 256
#define BUFFER_SIZE 512
#define BUFFER_SIZE_D 512

/***********************************************************************************************************************/
/*                                          Funzioni interne                                                           */
/***********************************************************************************************************************/
Node* shannonFanoEncode(Node *symbols[], int start, int end);

Node* shannonFanoDecode(Node *symbols[], int start, int end);

Node **createArrayOfPointerToNode(unsigned long int occurrences[], Node **symbols, unsigned long int countSymbols);

Node **createArrayOfPointerToNodeDecode(Node *lib[], Node **symbols, unsigned long int countSymbolsD);

Node **createArraySearch(Node **arraySearch, Node **symbolsD, int countSymbolsD, unsigned long int codeMax);

void createArrayOfPointerToNode256(Node *symbols256[], Node *symbols[], unsigned long int countSymbols);

unsigned long int createShannonFanoTree(Node *root, Node **symbols, unsigned long int countSymbols);

void bin(int i);

void setCode(Node *node, int direction);

unsigned long int setCanonicalCode(Node *symbols[], unsigned long int countSymbols);

void writeFileBitFileEncoded(Node *symbols256[], bit_file_t *fpIn, bit_file_t *fpOut);

void writeFileBitFileDecoded(long int bytesLeft, int bitsLastByte, Node **arraySearch, bit_file_t *fpIn, bit_file_t *fpOut);

void sortSymbolsArrayByOccurrences(Node **symbols, unsigned long int countSymbols);

unsigned long int createArrayOccurrencesBitFile(bit_file_t *fpIn, unsigned long int occurrences[]);

unsigned long int canonicalShannonFanoEncode(Node *symbols[], unsigned long int countSymbols);

void *searchSymbol(Node *arraySearch[], unsigned long int code, unsigned long int length);

int split(Node *symbols[], int start, int end);

int compareByOccurrence (const void * a, const void * b);

int compareByLengthAndASCII (const void * a, const void * b);

int getHeaderInformation(bit_file_t *fpIn, Node *lib[256], unsigned char buffer[256]);
/***********************************************************************************************************************/

/***********************************************************************************************************************
 *  Funzione per la codifica di un file con l'algoritmo di Shannon Fano Canonico
 *
 *  Parametri:
 *      - const char *fileInName: percorso del file da codificare (source)
 *      - const char *fileOutName: destinazione del file compresso (target)
 ***********************************************************************************************************************/
// void shannonFanoCanonicalEncode(const char *fileInName, const char *fileOutName)
void shannonFanoCanonicalEncode(char *fileInName, char *fileOutName)
{
    // apro il file da codificare
    bit_file_t *fpIn;
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Apro il file %s (da codificare)\n", fileInName);
    #endif
    
    if ((fpIn = BitFileOpen(fileInName, BF_READ)) == NULL)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante l'apertura del file %s\n", fileInName);
        #endif
        
        perror(fileInName);
        exit(EXIT_FAILURE);
    }
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("File %s aperto con successo\n", fileInName);
    #endif
    
    // creo il file codificato
    #ifdef _DEEP_DEBUG_SFC_
        printf("Creo il file codificato %s\n", fileOutName);
    #endif
    
    bit_file_t *fpOut;
    if ((fpOut = BitFileOpen(fileOutName, BF_WRITE)) == NULL)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante la creazione del file codificato (%s)\n", fileOutName);
        #endif
        
        perror(fileOutName);
        exit(EXIT_FAILURE);
    }
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("File %s creato con successo\n", fileOutName);
    #endif
    
    // leggo tutto il file e tengo conto delle occorrenze di ogni simbolo
    // Array che contiene le occorrenze di ogni codice ASCII
    unsigned long int occurrences[256] = {0};
    
    // Versione con BitFile
    unsigned long int countSymbols = createArrayOccurrencesBitFile(fpIn, occurrences);
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Occorrenze di ogni simbolo prese dal file %s\n", fileInName);
    #endif
    
    // array di puntatori a struttura Node
    // Array di puntatore alla struttura Node
    Node **symbols;
    if ((symbols = createArrayOfPointerToNode(occurrences, symbols, countSymbols)) == NULL) {
        #ifdef _DEBUG_SFC_
            printf("Errore durante l'allocazione dell'array dinamico symbols\n");
        #endif
        
        perror("Errore durante l'allocazione dell'array dinamico symbols");
        exit(EXIT_FAILURE);
    }
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Array di puntatori di dimensione variabile creato\n");
    #endif
    
    // ordino in base alle occorrenze
    qsort(symbols, countSymbols, sizeof(Node *), compareByOccurrence);
    
    // creo l'albero e genero il codice canonico di Shannon Fano
    Node *root;
    createShannonFanoTree(root, symbols, countSymbols);

    #ifdef _DEEP_DEBUG_SFC_
        printf("Albero di Shannon Fano creato\n");
    #endif
    
    // mi riposiziono all'inizio del file
    FILE *fpTemp = BitFileToFILE(fpIn);
    rewind(fpTemp);
    fpIn = MakeBitFile(fpTemp, BF_READ);
    
    // creo l'array di puntatori a Node. Alla posizione corrispondente al carattere 'a' ASCII
    // c'è il puntatore al simbolo del carattere 'a'
    // array per la scrittura
    Node *symbols256[256] = {NULL};
    createArrayOfPointerToNode256(symbols256, symbols, countSymbols);
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Array di puntatori di dimensione fissa (256) creato\n");
    #endif    
    
    // Scrivo il file codificato
    #ifdef _DEBUG_SFC_
        printf("Inizio la codifica ... ");
    #endif
    
    writeFileBitFileEncoded(symbols256, fpIn, fpOut);
    
    #ifdef _DEBUG_SFC_
        printf("codifica finita\n");
    #endif
    
    // chiudo i file
    #ifdef _DEEP_DEBUG_SFC_
        printf("Chiudo i file %s e %s\n", fileOutName, fileInName);
    #endif
    
    if (BitFileClose(fpOut) == EOF)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante la chiusura del file %s\n", fileOutName);
        #endif
        
        perror(fileOutName);
        exit(EXIT_FAILURE);
    }
    
    if (BitFileClose(fpIn) == EOF)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante la chiusura del file %s\n", fileInName);
        #endif
        
        perror(fileInName);
        exit(EXIT_FAILURE);        
    }
    
    // comunico la fine dell'esecuzione
    #ifdef _DEBUG_SFC_
        printf("File %s codificato con successo\n\n", fileOutName);
    #endif
}

/***********************************************************************************************************************
 *  Funzione per la decodifica di un file con l'algoritmo di Shannon Fano Canonico
 *
 *  Parametri:
 *      - const char *fileInName: percorso del file da codificare (source)
 *      - const char *fileOutName: destinazione del file compresso (target)
 ***********************************************************************************************************************/
// void shannonFanoCanonicalDecode(const char *fileInName, const char *fileOutName)
void shannonFanoCanonicalDecode(char *fileInName, char *fileOutName)
{
    // apro il file da decodificare
    bit_file_t *fpIn;
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Apro il file %s (da decodificare)\n", fileInName);
    #endif
    
    if ((fpIn = BitFileOpen(fileInName, BF_READ)) == NULL)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore nell'apertura del file %s\n", fileInName);
        #endif
        
        perror(fileInName);
        exit(EXIT_FAILURE);
    }
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("File %s aperto con successo\n", fileInName);
    #endif
    
    // creo il file decodificato
    #ifdef _DEEP_DEBUG_SFC_
        printf("Creo il file decodificato %s\n", fileOutName);
    #endif
    
    bit_file_t *fpOut;
    if ((fpOut = BitFileOpen(fileOutName, BF_WRITE)) == NULL)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante la creazione del file %s\n", fileOutName);
        #endif
        
        perror(fileOutName);
        exit(EXIT_FAILURE);
    }
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("File %s creato con successo\n", fileOutName);
    #endif
    
    #ifdef _DEBUG_SFC_
        printf("Inizio la decodifica ... ");
    #endif

    // prendo le informazioni dall'header del file codificato
    Node *lib[256] = {NULL};
    unsigned char bufferD[256];
    
    int countSymbolsD = getHeaderInformation(fpIn, lib, bufferD);
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Informazioni prese dall'header file %s\n", fileInName);
    #endif
    
    // alloco dinamicamente l'array di puntatori a simboli in base a quanti ne ho trovati all'interno del file
    // in questo modo riservo un po' di spazio e rendo più astratta la struttura dati
    Node **symbolsD;
    if ((symbolsD = createArrayOfPointerToNodeDecode(lib, symbolsD, countSymbolsD)) == NULL) {
        #ifdef _DEBUG_SFC_
            printf("Errore durante l'allocazione dell'array dinamico symbolsD\n");
        #endif
        
        perror("Errore durante l'allocazione dell'array dinamico symbolsD");
        exit(EXIT_FAILURE);
    }
    
    #ifdef _DEEP_DEBUG_SFC_
        printf("Array di puntatori di dimensione variabile creato\n");
    #endif
    
    // ricostruisco i codici in base alla loro lunghezza e tengo l'informazione di quello più lungo in una variabile
    // mi servirà per allocare dinamicamente l'array della ricerca (arraySearch)
    #ifdef _DEEP_DEBUG
        printf("Ricostruisco i codici dei simboli in base alla loro lunghezza/n")
    #endif 
    
    unsigned long int codeMax = canonicalShannonFanoEncode(symbolsD, countSymbolsD);

    // leggo il 257esimo char, che contiene l'informazione di quanti
    // bit leggere dall'ultimo byte
    int bitsLastByte = BitFileGetChar(fpIn);
    
    FILE *fpTemp = BitFileToFILE(fpIn);
    fseek(fpTemp, 0, SEEK_END);
    
    // calcolo quanti byte mi mancano da leggere
    long int bytesLeft = ftell(fpTemp) - 257;
    
    // mi riposiziono dopo le informazioni dell'header file
    fseek(fpTemp, 257*sizeof(char), SEEK_SET);
    
    // trasformo il puntatore a file in un puntatore a bit_file
    fpIn = MakeBitFile(fpTemp, BF_READ);

    // alloco la memoria per l'array di ricerca
    Node **arraySearch;
    if ((arraySearch = createArraySearch(arraySearch, symbolsD, countSymbolsD, codeMax)) == NULL)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante l'allocazione dell'array di ricerca (malloc)\n");
        #endif
        
        perror("Errore durante l'allocazione dell'array di ricerca (malloc)\n");
        exit(EXIT_FAILURE);
    }
    
    // Scrivo il file decodificato
    writeFileBitFileDecoded(bytesLeft, bitsLastByte, arraySearch, fpIn, fpOut);
    
    #ifdef _DEBUG_SFC_
        printf("decodifica finita\n");
    #endif
    
    // chiudo i file
    #ifdef _DEEP_DEBUG_SFC_
    printf("Chiudo i file %s e %s\n", fileOutName, fileInName);
    #endif
    
    if (BitFileClose(fpOut) == EOF)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante la chiusura del file %s\n", fileOutName);
        #endif
        
        perror(fileOutName);
        exit(EXIT_FAILURE);
    }
    
    if (BitFileClose(fpIn) == EOF)
    {
        #ifdef _DEBUG_SFC_
            printf("Errore durante la chiusura del file %s\n", fileInName);
        #endif
        
        perror(fileInName);
        exit(EXIT_FAILURE);        
    }
    
    // comunico la fine dell'esecuzione
    #ifdef _DEBUG_SFC_
        printf("File %s decodificato con successo\n\n", fileOutName);
     #endif
}

/***********************************************************************************************************************
 *  Funzione che riempie l'array delle occorrenze. Ad ogni indice corrisponde la relativa ricorrenza del simbolo
 *  all'interno del file
 *
 *  Parametri:
 *      - bit_file_t *fpIn: puntatore al file da leggere (input)
 *      - unsigned long int occurrences[]: array nel quale immagazzinare le informazioni
 ***********************************************************************************************************************/
unsigned long int createArrayOccurrencesBitFile(bit_file_t *fpIn, unsigned long int occurrences[])
{
    int countSymbols = 0;
    int symbol = 0;
    
    // leggo fino alla fine del file
    while ((symbol = BitFileGetChar(fpIn)) != EOF)
    {
        // se è la prima volta che trovo il simbolo, aumento il contatore
        if (!occurrences[symbol])
        {
            countSymbols++;
        }
        
        occurrences[symbol]++;
    }
    
    return countSymbols;
}

/***********************************************************************************************************************
 *  Funzione per la creazione dell'array di puntatori a nodo
 *
 *  Parametri:
 *      - unsigned long int occurrences[]: array delle occorrenze di ogni simbolo
 *      - Node **symbols: array allocato dinamicamente dei puntatori a nodo
 *      - unsigned long int countSymbols: simboli trovati all'interno del file
 * 
 *  Ritorno:
 *      - Node **symbols: array allocato dinamicamente per la decodifica
 ***********************************************************************************************************************/
Node **createArrayOfPointerToNode(unsigned long int occurrences[], Node **symbols, unsigned long int countSymbols)
{
    symbols = (Node **)calloc(sizeof(Node), countSymbols);
    Node *symbolTemp;
    
    unsigned int index = 0;
    for (int i=0; i<256; i++)
    {
        // se il simbolo è all'interno del file: creo il nodo e lo inserisco nell'array
        if (occurrences[i] != 0)
        {            
            symbolTemp = (Node *)malloc(sizeof(Node));
            symbolTemp->valueASCII = i;
            symbolTemp->count = occurrences[i];
            
            symbols[index++] = symbolTemp;
        }
    }
    
    // ritorno l'array allocato dinamicamente
    return symbols;
}

/***********************************************************************************************************************
 *  Funzione per la creazione dell'array di puntatori a nodo
 *
 *  Parametri:
 *      - unsigned long int occurrences[]: array delle occorrenze di ogni simbolo
 *      - Node **symbols: array allocato dinamicamente dei puntatori a nodo
 *      - unsigned long int countSymbols: simboli trovati all'interno del file
 * 
 *  Ritorno:
 *      - Node **symbols: array allocato dinamicamente per la decodifica
 ***********************************************************************************************************************/
Node **createArrayOfPointerToNodeDecode(Node *lib[], Node **symbolsD, unsigned long int countSymbolsD)
{
    symbolsD = (Node **)calloc(sizeof(Node), countSymbolsD);
    // riempio l'array di puntatori a nodo in base alle informazioni dell'header file
    int pos = 0;
    for (int i=0; i<256; i++)
    {
        if (lib[i] != NULL)
        {
            symbolsD[pos++] = lib[i];
        }
    }
    
    // ritorno l'array allocato dinamicamente
    return symbolsD;
}


/***********************************************************************************************************************
 *  Funzione per la creazione dell'array di puntatori a nodo che servirà per la decodifica
 *  In questo modo ho un array di 256 posizioni (0..255) e ad ogni indice corrisponde il valore ASCII del simbolo
 *
 *  Parametri:
 *      - Node *symbols256[]: array di 256 posizioni di puntatori a nodo
 *      - Node *symbols[]: array di dimensione variabile di puntatori a nodo
 *      - unsigned long int countSymbols: simboli trovati all'interno del file
 ***********************************************************************************************************************/
void createArrayOfPointerToNode256(Node *symbols256[], Node *symbols[], unsigned long int countSymbols)
{
    for (int i=0; i<countSymbols; i++)
    {
        symbols256[symbols[i]->valueASCII] = symbols[i];
    }
}

/***********************************************************************************************************************
 *  Funzione per la creazione dell'albero di Shannon Fano
 *  Crea l'albero, imposta i codici ad ogni simbolo e genera il codice canonico
 *
 *  Parametri:
 *      - Node *root: la radice dell'albero
 *      - Node **symbols: array allocato dinamicamente di puntatori a nodo
 *      - unsigned long int countSymbols: simboli trovati all'interno del file
 ***********************************************************************************************************************/
unsigned long int createShannonFanoTree(Node *root, Node **symbols, unsigned long int countSymbols)
{
    // creo l'albero
    root = shannonFanoEncode(symbols, 0, (int)countSymbols-1);
    
    // imposto i codici di Shannon Fano
    setCode(root, 2);
    
    // creo i codici di Shannon Fano canonico
    unsigned long int codeMax = canonicalShannonFanoEncode(symbols, countSymbols);
    
    // ritorno il codice con lunghezza massima per poi creare l'array di ricerca (array search)
    return codeMax;
}

int binToInt(int move[], int size);

/***********************************************************************************************************************
 *  Funzione che divide in modo opportuno in base alla somma delle occorrenze
 *  Trovo il simbolo che fa "sbilanciare" le occorrenze e controllo se è meglio mettero nel sotto albero di
 *  sinistra oppure nel sotto albero di destra
 *
 *  Parametri:
 *      - Node *symbols[]: array di puntatori a nodo da dividere
 *      - int start: da che indice prendere l'array
 *      - int end: fino a che indice prendere l'array
 *
 *  Ritorno:
 *      - int index: se l'elemento che fa "sbilanciare" la divisione deve andare a sinistra, ritorna l'indice
 *                   altrimenti ritorna l'indice-1
 ***********************************************************************************************************************/
int split(Node *symbols[], int start, int end)
{
    int totalCount = 0;
    int middle = 0;
    int countByLeft = 0;
    int countByRight = 0;
    
    // sommo tutte le occorrenze
    for (int i=start; i<(end+1); i++)
    {
        totalCount += symbols[i]->count;
    }
    
    // cerco la metà delle occorrenze
    middle = totalCount/2;
    
    // sommo le occorrenze a partire da sinistra
    int left = start;
    while (countByLeft <= middle)
    {
        countByLeft += symbols[left]->count;
        left++;
    }
    
    int index = left-1;

    for (int right = (left-1); right<(end+1); right++)
    {
        countByRight += symbols[right]->count;
    }
    
    if (countByLeft < countByRight)
    {
        // l'elemento che fa "sbilanciare" va a sinistra
        return index;
    }
    else
    {
        // l'elemento che fa "sbilanciare" va a destra
        return index-1;
    }
}

/***********************************************************************************************************************
 *  Funzione che crea l'albero di Shannon Fano
 *
 *  Parametri:
 *      - Node *symbols[]: array dei simboli trovati
 *      - int start: da che indice prendere l'array
 *      - int end: fino a che indice prendere l'array
 ***********************************************************************************************************************/
Node* shannonFanoEncode(Node *symbols[], int start, int end)
{
    if (start == end)
    {
        return symbols[start];
    }
    else
    {
        int positioToSplit = split(symbols, start, end);
        
        Node *newNode = (Node *)malloc(sizeof(Node));
        // newNode->valueASCII = 64;
        newNode->left = shannonFanoEncode(symbols, start, positioToSplit);
        newNode->right = shannonFanoEncode(symbols, positioToSplit+1, end);
        
        return newNode;
    }
}

/***********************************************************************************************************************
 *  Funzione per la generazione del codice canonico
 *  Ordina l'array dei simboli in base alla lunghezza del codice e al carattere ASCII
 *
 *  Parametri:
 *      - Node *symbols[]: array da ordinare
 *      - unsigned long int countSymbols: simboli trovati all'interno del file
 ***********************************************************************************************************************/
unsigned long int canonicalShannonFanoEncode(Node *symbols[], unsigned long int countSymbols)
{
    // ordino l'array in base alla lunghezza dei codici
    qsort(symbols, countSymbols, sizeof(Node *), compareByLengthAndASCII);
    
    // imposto il codice canonico di Shannon Fano
    unsigned long int codeMax = setCanonicalCode(symbols, countSymbols);
   
    // ritorno il codice con lunghezza massima
    return codeMax;
}

/***********************************************************************************************************************
 *  Funzione che trasforma da un array di interi (0 o 1) in un intero
 *
 *  Parametri:
 *      - int move[]: array che tiene immagazzinati tutti gli spostamenti mentre si percorre l'albero
 *      - int size: dimensione dell'array
 ***********************************************************************************************************************/
int binToInt(int move[], int size)
{
    int power = 0;
    int code = 0;

    for (int i=size-1; i>=0; i--)
    {
        code += move[i]*pow(2, power++);
    }
    
    return code;
}

/***********************************************************************************************************************
 *  Funzione che scorre tutto l'albero di Shannon Fano e imposta i codici e le lunghezze per ogni simbolo
 *
 *  Parametri:
 *      - Node *node: puntatore al nodo (radice)
 *      - int direction: indica da dove arriva il nodo  0: sinistra
 *                                                      1: destra
 *                                                      2: root
 ***********************************************************************************************************************/
void setCode(Node *node, int direction)
{
    // tiene conto dei passi fatti
    int static pos = 0;
    
    // tiene conto di tutti i passi fatti mentre si scorre l'albero
    int static move[MAX_LENGTH_CODE] = {0};
    
    if(node != NULL)
    {
        if (direction != 2)
        {
            pos++;
        }
        
        node->shannonFanoCode = binToInt(move, pos);

        // 
        memcpy(node->shannonFanoBinCode, move, pos*sizeof(int));

        // lungezza del codice
        node->length = pos;

        move[pos] = 0;        
        setCode(node->left, 0);


        move[pos] = 1;
        setCode(node->right, 1);

        if (direction != 2)
        {
            pos--;
        }
    }
}

/***********************************************************************************************************************
 *  Funzione per la generazione del codice canonico in base alle lunghezze generate dall'albero di Shannon Fano
 *
 *  Parametri:
 *      - Node *symbols[]: array che contiene i simboli
 *      - unsigned char countSymbols: numero di simboli trovati all'interno del file
 ***********************************************************************************************************************/
unsigned long int setCanonicalCode(Node *symbols[], unsigned long int countSymbols)
{
    // codice con la lunghezza massima
    unsigned long int maxCode = 0;
    
    // il primo codice è per costruzione "0"
    symbols[0]->canonicalCode = 0;
    
    for (int i=1; i<countSymbols; i++)
    {
        if (symbols[i]->length  == symbols[i-1]->length)
        {
            symbols[i]->canonicalCode = symbols[i-1]->canonicalCode + 1;
        }
        else
        {
            symbols[i]->canonicalCode = (symbols[i-1]->canonicalCode + 1) << (symbols[i]->length - symbols[i-1]->length);
        }
        
        // se necessario, aggiorno il valore del codice con la lunghezza massima
        if (maxCode < symbols[i]->canonicalCode)
        {
            maxCode = symbols[i]->canonicalCode;
        }
    }
    
    return maxCode;
}

/***********************************************************************************************************************
 *  Funzione per la scrittura del file codificato
 *
 *  Parametri:
 *      - Node *symbols256[]: array di puntatori che contiene le informazioni necessarie su ogni simbolo
 *      - bit_file_t *fpIn: puntatore al file di input
 *      - bit_file_t *fpOut: puntatore al file di output
 ***********************************************************************************************************************/
void writeFileBitFileEncoded(Node *symbols256[], bit_file_t *fpIn, bit_file_t *fpOut)
{
    unsigned int c;
    Node *symbol;
    
    // scrivo la lunghezza dei codici sul file codificato
    for (int i=0; i<256; i++)
    {
        if (symbols256[i] == NULL)
        {
            // se il simbolo non è presente nella mia lista, ho un puntatore nullo
            // quindi sul file scrivo la lunghezza pari a 0
            BitFilePutChar(0, fpOut);
        }
        else
        {
            // altrimenti prendo la lunghezza del codice con cui è stato codificato
            // il simbolo e scrivo il valore sul file
            BitFilePutChar((unsigned char)symbols256[i]->length, fpOut);
        }
    }
    
    // scrivo alla posizione 256 il valore 0 che sarà poi rimpiazzato dal valore di 
    // quanti bit leggere dall'ultimo byte
    BitFilePutChar(0, fpOut);
    
    unsigned long int bitsWritten = 0;
    int bitToWrite = 0;
    while ((c = BitFileGetChar(fpIn)) != EOF)
    {
        // prendo il simbolo corrispondente al carattere letto
        symbol = symbols256[c];
        
        for (int i=(int)symbol->length-1; i >= 0; i--)
        {
            // preparo il bit da scrivere
            bitToWrite = (symbol->canonicalCode >> i) & 1;
            
            // scrivo bit a bit
            BitFilePutBit(bitToWrite, fpOut);
            
            // ogni volta che scrivo un bit, tengo il conto
            bitsWritten++;
            
            // ogni volta che scrivo un multiplo di 8 bit vuol dire che ho scritto un byte, quindi
            // azzero il contatore
            if (!(bitsWritten % 8))
            {
                bitsWritten = 0;
            }
        }
    }
    
    // bit da leggere dall'ultimo byte
    int bitsToRead = (int)bitsWritten;
    
    // mi sposto alla posizione 256 per scrivere il valore nel byte
    FILE *fpTemp = BitFileToFILE(fpOut);    
    fseek(fpTemp, 256*sizeof(unsigned char), SEEK_SET);
    fpOut = MakeBitFile(fpTemp, BF_WRITE);
    
    // scrivo sul file il valore
    BitFilePutChar(bitsToRead, fpOut);
}

/***********************************************************************************************************************
 *  Funzione per la scrittura del file decodificato
 *
 *  Parametri:
 *      - long int bytesLeft: byte restanti da leggere e da decodificare
 *      - int bitsLastByte: bit da leggere dall'ultimo byte
 *      - bit_file_t *fpIn: puntatore al file di input
 *      - bit_file_t *fpOut: puntatore al file di output
 ***********************************************************************************************************************/
void writeFileBitFileDecoded(long int bytesLeft, int bitsLastByte, Node **arraySearch, bit_file_t *fpIn, bit_file_t *fpOut)
{
    int bitTemp;                    // bit temporaneo
    long int lengthCodeTemp = 0;    // lunghezza del codice temporaneo
    long int codeTemp = 0x00;       // valore del codice temporaneo
    long int bitsRead = 0;          // conteggio dei bits letti
    Node *symbolTemp;
    
    // analizzo il file fino a quando non mi restano più byte da leggere
    while (bytesLeft != 0)
    {
        // se sono all'ultimo byte e i bit da leggere non sono 0
        if (bytesLeft == 1 && bitsLastByte !=0)
        {
            int bitsReadLastByte = 0;   // conteggio dei bit letti dall'ultimo byte
            
            // fino a quando i bits letti sono diversi da quanti ne devo effettivamente leggere
            while (bitsReadLastByte != bitsLastByte)
            {
                // prendo il bit temporaneo
                int tempBitLastByte = BitFileGetBit(fpIn);
                
                // preparo lo spazio per il bit
                codeTemp <<= 1;                
                lengthCodeTemp++;
                
                // lo aggiungo al codice temporaneo
                codeTemp |= tempBitLastByte;
                bitsReadLastByte++;
                
                // controllo se esiste il codice
                if ((symbolTemp = searchSymbol(arraySearch, codeTemp, lengthCodeTemp)) != NULL) {
                    // scrivo il simbolo
                    
                    #ifdef _DEEP_DEBUG_SFC_
                        printf("Simbolo %c trovato -> lo scrivo sul file\n", symbolTemp->valueASCII);
                    #endif
                    
                    BitFilePutChar(arraySearch[codeTemp]->valueASCII, fpOut);
                    
                    // azzero il codice temporaneo e la lunghezza
                    codeTemp = 0x00;
                    lengthCodeTemp = 0;
                }
            }
            
            // esco dal while
            bytesLeft = 0;
        }
        else // altrimenti lo analizzo come se fosse un qualsiasi byte
        {    
            // prendo il bit temporaneo
            bitTemp = BitFileGetBit(fpIn);
            
            // aggiorno il valore del codice temporaneo e la sua lunghezza
            codeTemp <<= 1;
            codeTemp |= bitTemp;
            lengthCodeTemp++;
            
            // incremento il numero di bit letti
            bitsRead++;
            
            // ogni byte letto, decremento i byte restanti
            if ((bitsRead % 8)  == 0) 
            {
                bytesLeft--;
            }
            
            // controllo se esiste il codice
            if ((symbolTemp = searchSymbol(arraySearch, codeTemp, lengthCodeTemp)) != NULL) {
                // scrivo il simbolo
                
                #ifdef _DEEP_DEBUG_SFC_
                    printf("Simbolo %c trovato -> lo scrivo sul file\n", symbolTemp->valueASCII);
                #endif
                
                BitFilePutChar(arraySearch[codeTemp]->valueASCII, fpOut);
                
                // azzero il codice temporaneo e la lunghezza
                codeTemp = 0x00;
                lengthCodeTemp = 0;
            }
        }
    }
}

/***********************************************************************************************************************
 *  Funzione per la ricerca di un simbolo all'interno dell'array per la decodifica
 *
 *  Parametri:
 *      - Node *arraySearch[]: array di ricerca.
 *                             Gli indici corrispondono al codice mentre il valore a quella posizione
 *                             è il simbolo. In questo modo la ricerca viene velocizzata al massimo anche se si
 *                             "spreca" un po' di memoria.
 *      - unsigned long int code: codice da cercare
 *      - unsigned long int length: lunghezza del codice 
 *
 *  Ritorno:
 *      - Node *symbol: puntatore al symbolo se viene trovato all'interno dell'array un simbolo con lo stesso codice
 *                      e con la stessa lunghezza
 *      - void *symbol: se il symbolo non viene trovato all'interno dell'array
 ***********************************************************************************************************************/
void *searchSymbol(Node *arraySearch[], unsigned long int code, unsigned long int length)
{
    // creo un puntatore a Node
    Node *symbol = NULL;
    
    if (arraySearch[code] != NULL &&
        code == arraySearch[code]->canonicalCode &&
        length == arraySearch[code]->length)
    {
        symbol = arraySearch[code];
        
    }
    
    // ritorno il puntatore
    return symbol;
}

/***********************************************************************************************************************
 *  Funzione di confronto per l'ordinamento con il qsort di sistema. Ordina in base alle ricorrenze dei
 *  simboli all'interno del file.
 *
 *  Parametri:
 *      - char void *a: puntatore vuoto (da castare in base al tipo di dato nell'array) del primo elemento
 *      - char void *b: puntatore vuoto (da castare in base al tipo di dato nell'array) del secondo elemento
 *
 *  Ritorno:
 *      - int: valore positivo se a < b
 *             0 se a = b
 *             valore negativo se a > b
 ***********************************************************************************************************************/
int compareByOccurrence (const void * a, const void * b) {
    return (int)((*(Node **)b)->count - (*(Node **)a)->count);
}

/***********************************************************************************************************************
 *  Funzione di confronto per l'ordinamento con il qsort di sistema. 
 *
 *  Parametri:
 *      - char void *a: puntatore vuoto (da castare in base al tipo di dato nell'array) del primo elemento
 *      - char void *b: puntatore vuoto (da castare in base al tipo di dato nell'array) del secondo elemento
 *
 *  Ritorno:
 *      - int: 1    1) ASCII a > ASCII b e la lunghezza dei codici di a e b è uguale
 *                  2) lunghezza del codice di a > lunghezza del codice di b
 *             altrimenti
 ***********************************************************************************************************************/
int compareByLengthAndASCII (const void * a, const void * b) {
    Node *nodeA = (*(Node **)a);
    Node *nodeB = (*(Node **)b);
    
    if (nodeA->length == nodeB->length &&
        nodeA->valueASCII > nodeB->valueASCII)
    {
        return 1;
    }
    else if(nodeA->length > nodeB->length)
    {
        return 1;
    }
    else
    {
        return -1;
    }
}
/***********************************************************************************************************************
 *  Funzione che ritorna le informazioni dell'header file
 *
 *  Parametri:
 *      - bit_file_t *fpIn: codice da decodificare
 *      - Node *lib[]: array che conterrà le informazioni necessarie per la decodifica
 *      - unsigned char buffer[]: buffer di lettura
 *
 *  Ritorno:
 *      - int countSymbolsD: numero totale di simboli trovati all'interno dell'header file
 ***********************************************************************************************************************/

int getHeaderInformation(bit_file_t *fpIn, Node *lib[256], unsigned char buffer[256])
{
    Node *symbolTemp;
    int countSymbolsD = 0;
    for (int i=0; i<256; i++)
    {
        // prendo la lunghezza del codice dal file
        buffer[i] = BitFileGetChar(fpIn);
        
        // se il codice è da decodificare allocco il puntatore
        if (buffer[i] != 0)
        {
            symbolTemp = (Node *)malloc(sizeof(Node));
            symbolTemp->valueASCII = i;
            symbolTemp->length = buffer[i];
            
            lib[countSymbolsD++] = symbolTemp;
        }
    }
    
    return countSymbolsD;
}

/***********************************************************************************************************************
 *  Funzione che crea l'array per la ricerca dei simboli
 *
 *  Parametri:
 *      - Node **arraySearch: puntatore all'array di ricerca
 *      - Node **symbolsD: array di puntatori a simboli
 *      - int countSymbolsD: simboli trovati nel file da decodificare
 *      - unsigned long int codeMax
 *
 *  Ritorno:
 *      - Node **arraySearch: puntatore all'array di ricerca
 ***********************************************************************************************************************/
Node **createArraySearch(Node **arraySearch, Node **symbolsD, int countSymbolsD, unsigned long int codeMax)
{
    // alloco la memoria per l'array di ricerca
    arraySearch = (Node **)malloc(codeMax*sizeof(Node));
    
    // riempio l'array della ricerca
    for (int i=0; i<countSymbolsD; i++)
    {
        arraySearch[symbolsD[i]->canonicalCode] = symbolsD[i]; 
    }
    
    return arraySearch;
}